package leetcode.editor.cn;
//给你一个按 非递减顺序 排列的整数数组 nums 。 
//
// 请你判断是否能在将 nums 分割成 一个或多个子序列 的同时满足下述 两个 条件： 
//
// 
// 
// 
// 每个子序列都是一个 连续递增序列（即，每个整数 恰好 比前一个整数大 1 ）。 
// 所有子序列的长度 至少 为 3 。 
// 
// 
// 
//
// 如果可以分割 nums 并满足上述条件，则返回 true ；否则，返回 false 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,3,3,4,5]
//输出：true
//解释：nums 可以分割成以下子序列：
//[1,2,3,3,4,5] --> 1, 2, 3
//[1,2,3,3,4,5] --> 3, 4, 5
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,3,3,4,4,5,5]
//输出：true
//解释：nums 可以分割成以下子序列：
//[1,2,3,3,4,4,5,5] --> 1, 2, 3, 4, 5
//[1,2,3,3,4,4,5,5] --> 3, 4, 5
// 
//
// 示例 3： 
//
// 
//输入：nums = [1,2,3,4,4,5]
//输出：false
//解释：无法将 nums 分割成长度至少为 3 的连续递增子序列。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10⁴ 
// -1000 <= nums[i] <= 1000 
// nums 按非递减顺序排列 
// 
//
// Related Topics 贪心 数组 哈希表 堆（优先队列） 👍 444 👎 0


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution171 {

    /**
     * 检查序列是否可以被分成长度至少为 3 的连续子序列
     * 每个子序列中不同的整数数量要相同
     *
     * @param nums 检查的序列
     * @return 序列能够被组成子序列返回 true，否则返回 false
     */
    public boolean isPossible(int[] nums) {
        HashMap<Integer, Integer> freq = new HashMap<>();
        HashMap<Integer, Integer> need = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        for (int num : nums) {
            if (freq.get(num) == 0) {
                continue;
            }

            if (need.containsKey(num) && need.get(num) > 0) {
                freq.put(num, freq.get(num) - 1);
                need.put(num, need.get(num) - 1);
                need.put(num + 1, need.getOrDefault(num + 1, 0) + 1);
            } else if (freq.containsKey(num) && freq.get(num) > 0
                    && freq.containsKey(num + 1) && freq.get(num + 1) > 0
                    && freq.containsKey(num + 2) && freq.get(num + 2) > 0) {
                freq.put(num, freq.get(num) - 1);
                freq.put(num + 1, freq.get(num + 1) - 1);
                freq.put(num + 2, freq.get(num + 2) - 1);
                need.put(num + 3, need.getOrDefault(num + 3, 0) + 1);

            } else {
                return false;
            }
        }
        return true;
    }


    /**
     * 检查给定的数组是否可以分割成若干子序列，要求每个子序列长度 >= 3，
     * 相同数字不能出现在同一个子序列中。
     * <p>
     * 思路：贪心 + 哈希表，以哈希表 {number: frequency} 维护每个数字出现的频率，
     * 再以哈希表 {end: list} 维护每个以 end 为结尾的子序列，
     * 尝试向已有的子序列中添加数字，若没有已有子序列，尝试在 nums 中新建一个包含
     * 连续的三个数的子序列。
     * <p>
     * 时间复杂度：O(N)
     * 空间复杂度：O(N)
     */
    public boolean isPossible1(int[] nums) {
        // 统计每个数字出现的频率
        Map<Integer, Integer> freq = new HashMap<>();
        for (int v : nums) freq.put(v, freq.getOrDefault(v, 0) + 1);

        // 以哈希表 {end: list} 维护每个以 end 为结尾的子序列
        Map<Integer, List<List<Integer>>> need = new HashMap<>();

        for (int v : nums) {
            if (freq.get(v) == 0) {
                continue;
            }

            if (need.containsKey(v) && !need.get(v).isEmpty()) {
                // 如果已经存在以 v - 1 结尾的子序列，就将当前 v 接到它后面
                freq.put(v, freq.get(v) - 1);
                // 取出需要 v 的最短子序列
                List<Integer> seq = need.get(v).remove(need.get(v).size() - 1);
                seq.add(v);
                // 将更新后的子序列添加到 map 中
                if (!need.containsKey(v + 1)) {
                    need.put(v + 1, new ArrayList<>());
                }
                need.get(v + 1).add(seq);

            } else if (freq.get(v) > 0 && freq.getOrDefault(v + 1, 0) > 0
                    && freq.getOrDefault(v + 2, 0) > 0) {
                // 否则如果存在 v, v + 1, v + 2，就新建一个以 v, v + 1, v + 2 为顺序的子序列
                freq.put(v, freq.get(v) - 1);
                freq.put(v + 1, freq.get(v + 1) - 1);
                freq.put(v + 2, freq.get(v + 2) - 1);
                List<Integer> seq = new ArrayList<>();
                seq.add(v);
                seq.add(v + 1);
                seq.add(v + 2);
                // 将更新后的子序列添加到 map 中
                if (!need.containsKey(v + 3)) {
                    need.put(v + 3, new ArrayList<>());
                }
                need.get(v + 3).add(seq);

            } else {
                // 如果既没有可以接到的子序列，也无法新建新的子序列，则返回 false
                return false;
            }
        }

        // 遍历所有序列，检查它们的长度是否都大于等于 3，如果有一个短于 3 则返回 false
        for (List<List<Integer>> allSeq : need.values()) {
            for (List<Integer> seq : allSeq) {
                if (seq.size() < 3) {
                    return false;
                }
            }
        }

        // 如果所有序列长度都大于等于 3，则返回 true
        return true;
    }


}
//leetcode submit region end(Prohibit modification and deletion)
